#leetcode题目416：分割等和子集
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(1)

from typing import List
    
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        """
        分割等和子集
        给你一个只包含正整数的非空数组 nums。
        请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
        """
        # 计算数组总和
        total_sum = sum(nums)
        
        # 如果总和为奇数，无法分割成两个等和子集
        if total_sum % 2 == 1:
            return False
        
        # 目标值：每个子集的和应该是总和的一半
        target = total_sum // 2
        
        # dp[i] 表示能否组成和为 i 的子集
        dp = [False] * (target + 1)
        dp[0] = True  # 和为0总是可以组成（不选任何元素）
        
        # 遍历每个数字
        for num in nums:
            # 从后往前遍历，避免重复使用同一个数字
            for j in range(target, num - 1, -1):
                # 状态转移：dp[j] = dp[j] || dp[j - num]
                # 要么之前就能组成j，要么现在用num能组成j
                dp[j] = dp[j] or dp[j - num]
        
        return dp[target]





#测试数据
nums = [1,5,11,5]
#预期输出：true,可以分割成[1,5,5]和[11]
solution = Solution()
print(solution.canPartition(nums))

nums = [1,2,3,5]
#预期输出：false,无法分割成两个等和子集
solution = Solution()
print(solution.canPartition(nums))